package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述：
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-07 16:26
 */
public class GenerateParenthesis {

    private static ArrayList[] cache = new ArrayList[100];

    private List<String> list = new ArrayList<>();

    public static void main(String[] args) {
//        List<String> strings3 = generateParenthesis2(1);
//        System.out.println(strings3);
//        List<String> strings2 = generateParenthesis2(2);
//        System.out.println(strings2);
//        List<String> strings = generateParenthesis2(3);
//        System.out.println(strings);
//        Iterator<String> iterable = strings.iterator();
//        while (iterable.hasNext()){
//            String ss = iterable.next();
//            if(ss.charAt(ss.length()-1) == '0'){
//                iterable.remove();
//            }
//        }
//        System.out.println(strings);

        //System.out.println(insertRandom("123", "4"));

        System.out.println(generateParenthesisMy(1));


    }

    public static List<String> generateParenthesisMy(int n) {
        List<String> list = new ArrayList<>();
        if (n == 0) {
            return list;
        }
        generate2(n, n, "",list);
        return list;
    }

    //回溯法   左括号数必须大于大括号数  左括号数小于n
    public static void generate2(int left, int right, String str,List<String> list) {
        if (left == right) {
            if (left == 0) {
                list.add(str);
                return;
            }
            generate2(left - 1, right, str + "(",list);
        } else {
            if (left > 0) {
                generate2(left - 1, right, str + "(",list);
            }
            generate2(left, right - 1, str + ")",list);
        }
    }

    public static List<String> generate(int n) {
        if (cache[n] != null) {
            return cache[n];
        }
        ArrayList<String> ans = new ArrayList<String>();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c) {
                for (String left : generate(c)) {
                    for (String right : generate(n - 1 - c)) {
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        cache[n] = ans;
        return ans;
    }

    // 其实考的就是 n 有多少种组合 再将组合变换成具体字符即可
    public static List<String> generateParenthesis2(int n) {
        List<String> list = new ArrayList<>();
        if (n == 1) {
            list.add("1");
            return list;
        }
        list.addAll(insertRandom(buildZero(n), n));
        for (int i = 1; i < n; i++) {
            List<String> strings = generateParenthesis2(i);
            for (int j = 0; j < strings.size(); j++) {
                list.addAll(insertRandom(strings.get(j), (n - i)));
            }
        }
        return list;
    }

    //将b 随机插到a的某个位置
    public static List<String> insertRandom(String a, Object b) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i <= a.length(); i++) {
            String ss = a.substring(0, i) + b + a.substring(i);
            list.add(ss);
        }
        return list;
    }

    //补0
    public static String buildZero(int n) {
        String ss = "";
        for (int i = 0; i < n - 1; i++) {
            ss += "0";
        }
        return ss;
    }

}
